package com.test.daily.leetcode.y2022.m07.day0715.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/15 上午 08:44
 * @version: 1.0
 */
public class Solution {
    public static void countSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.min(max, arr[i]);
        }
        int[] counts = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i]]++;
        }
        int j = 0;
        for (int i = 0; i < counts.length; i++) {
            if (counts[i]-- > 0) {
                arr[j++] = i;
            }
        }
    }

    // 獲取最多的位數
    public static int getMaxBits(int i) {
        int res = 0;
        while (i > 0) {
            res++;
            res /= 10;
        }
        return res;
    }

    // 獲取對應位置的數字
    public static int getDigital(int value, int num) {
        return (int) ((value / Math.pow(10, num - 1)) % 10);
    }

    public static void radixSort(int[] arr, int L, int R) {
        int digit = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            digit = Math.max(digit, getMaxBits(arr[i]));
        }
        int[] help = new int[R - L + 1];
        int[] count = new int[10];
        for (int d = 1; d <= digit; d++) {
            for (int i = L; i < R; i++) {
                int j = getDigital(arr[i], d);
                count[j]++;
            }
            for (int j = 1; j < 10; j++) {
                arr[j] += arr[j-1];
            }

        }

    }
}
